/**
File:           MF.java
Author:         T.S.Yo
Last Modified:  2006.11.03
Purpose:
    For a one-dimensional Cellular Automata problem, we are interested in finding local rules for majority function (if more than half are 1's, then vote for 1, otherwise vote for 0), and these rules consider only the target bit and its neighbours.  Before looking for optimal rules, we would like to know how many steps, M, is required to make a bit string converge, with respect to the bit string length, N, and neighbours on each side to be considered, r.
    This small program generates random rules and random initial bit-strings to test how many times each rule needs to be applied to make the bit-strings converge into uniform bit-strings.

Ref: Mitchell, M., Crutchfield, J.P. & Hraber, P.T. (1994). Evolving cellular automata to perform computations: Mechanisms and impediments. Physica D, 75:361-391.    
**/
import java.util.*;

public class MF{
//----------------------------------------------------------------------
// Constructor
//----------------------------------------------------------------------
//    public MF(final int N, final int r, final int nIC, final int nRules){}
//----------------------------------------------------------------------
// Initializer
//----------------------------------------------------------------------
    /* Generate all initial configurations with length of n    */
    public int[][] allIC_Generate(final int n)
    {
        int[][] allIC;          // ICs to return
        int mIC;
        
        // If configuration-length is small enough, generate all rules
        if( n <= 16 )
        {
            System.out.print("\nTotally 2^"+n+" configurations exist, generate all....\n");
            mIC = (int)Math.pow(2.,(double)n);
            allIC = new int[mIC][];
            for(int i=0; i < mIC; i++)
            {
                // Convert i into n-bit binary string
                allIC[i] = intToBitArray(n,(int)i);
            }
        // If configuration-length is too large, generate configurations with multiple indexing in tree structure
        } else {
            System.out.print("\nTotally 2^"+n+" configurations exist. It is too big for indexing, randomly generate 100 instead\n");
            allIC = IC_Generate(n,100);
        }        
         
        return allIC;
    }

    /* Randomly generate nIC initial configurations:
         n      : length of configuration
         nIC    : number of configurations wanted*/
    public int[][] IC_Generate(final int n, final int nIC)
    {
        int[][] allIC;          // ICs to return
        int mIC = nIC;
        
        // Check IC_flag
        Random rand = new Random();
        allIC = new int[mIC][n];
        for(int i=0; i < mIC; i++)
        {
            for(int m = 0; m < n; m++)
            {
                allIC[i][m] = rand.nextInt(2);
            }
        }
        // Output for testing
        //for(int i = 0; i < mIC; i++){
        //    System.out.println(i+": "+intArrayToString(allIC[i]));
        //} 
        return allIC;
    }

    /* Generate rules */
    public int[][] ruleGenerate(final int r, int numRules)
    {
        int ruleLength = (int)Math.pow(2.,(double)(2*r+1));
        int[][] allRules;
                Random rand = new Random();
        allRules = new int[numRules][ruleLength];
        for(int k = 0; k < numRules; k++)
        {
            for(int l = 0; l < ruleLength; l++)
            {
                allRules[k][l] = rand.nextInt(2);
            }
        }
        // Output for testing
        //for(int k = 0; k < numRules; k++){
        //    System.out.println(k+": "+intArrayToString(allRules[k]));
        //}  
              
        return allRules;
    }
    
    public int[][] allRuleGenerate(final int r)
    {
        // Define size of rules: (2r+1) bits, 2^(2r+1) combinations, therefore 2^2^(2r+1) rules
        int ruleLength = (int)Math.pow(2.,(double)(2*r+1));
        int[][] allRules;
        int numRules = 10;
        
        // If rule-length is small enough, generate all rules
        if( ruleLength <= 16 )
        {
            System.out.print("\nTotally 2^"+ruleLength+" rules exist, generate all....\n");
            numRules = (int)Math.pow(2.,(double)(ruleLength));
            allRules = new int[numRules][ruleLength];
            for(int k = 0; k < numRules; k++)
            {
                allRules[k] = intToBitArray(ruleLength,k);
            }
        // If rule-length is too large, randomly generate rules
        } else {
            System.out.print("\nTotally 2^"+ruleLength+" rules exist. It is too big for indexing, randomly generate "+numRules+" instead\n");
            Random rand = new Random();
            allRules = new int[numRules][ruleLength];
            for(int k = 0; k < numRules; k++)
            {
                for(int l = 0; l < ruleLength; l++)
                {
                    allRules[k][l] = rand.nextInt(2);
                }
            }
        }
        // Output for testing
        //for(int k = 0; k < numRules; k++){
        //    System.out.println(k+": "+intArrayToString(allRules[k]));
        //}  
              
        return allRules;
    }
    
    /* Apply a rule to a configuration */
    // Update procedure:
    //  1. Extract sub-bit-array
    //  2. Look up for new site state by sub-array
    //  3. Insert output bit to new configuration
    public int[] ruleApply(final int r, final int[] rule, final int[] config)
    {
        final int confL = config.length;
        final int subL  = 2 * r + 1;
        int[] newConfig = new int[confL];
        int[] subArray = new int[subL]; 
        
        // Check: rule length == 2^subL
        if (rule.length!=(int)Math.pow(2.,(double)subL))
        {
            System.out.println("\nRule-length and r do not match, rule can not be applied!");
            System.exit(1);
            //return config;
        }
        
        // Make up a periodic configuration by copying r bits to both side
        int[] pConfig = new int[confL+2*r];
        //   0 ~ r-1: left side read from right end
        for(int i=0; i<r;i++) {pConfig[i] = config[confL-r+i];}
        //  r ~ confL-r: regular
        for(int i=r; i<(confL+r);i++) {pConfig[i] = config[i-r];}
        // confL-r ~ confL: right side read from left end
        for(int i=(confL+r); i<(confL+2*r);i++)  {pConfig[i] = config[(i-confL-r)];}
        
        // Update
        int newSiteIdx;
        for(int j = 0; j < confL; j++)
        {
            // Extract sub-bit-array
            for(int k = 0; k < subL; k++)
            {
                subArray[k] = pConfig[j+k];
            }
            // Look up for output bit
            newSiteIdx = bitArrayToInt(subArray);
            // Insert the output bit to new configuration
            newConfig[j] = rule[newSiteIdx];
            
            /*
            // output for testing
            System.out.println("Sub-Config "+j+": "+intArrayToString(subArray));
            System.out.println("RuleIndex: "+newSiteIdx);
            System.out.println("Output-Bit: "+newConfig[j]);
            */
        }
        
        // Return new configuration
        return newConfig;
    }

    /* Check convergence of a rule-configuration pair */
    public int[] checkConvergence(final int r, final int maxStep, 
                                    final int[] rule, final int[] config)
    {
        int[] convgMsg = new int[2];
        int step = 0;
        int cfgL = config.length;
        
        // 
        int sum;
        int[] newConfig = new int[cfgL];
        int[] tmpConfig = copyIntArray(config);
        while(step <= maxStep)
        {
            // Apply rule to current configuration
            newConfig = ruleApply(r,rule,tmpConfig);
            
            // output for testing
            //System.out.println(step+" NewConfig: "+": "+intArrayToString(newConfig));
            
            
            // Check convergence
            sum = sumIntArray(newConfig);
            if((sum==0)||(sum==cfgL))
            {
                convgMsg[0] = (int)(sum/cfgL);
                convgMsg[1]++;
                break;
            }
            // Check if rule change configuration at all
            if(isTwoConfigEqual(tmpConfig,newConfig))
            {
                convgMsg[0] = -1;
                break;
            }
            // For next iteration
            tmpConfig = copyIntArray(newConfig);
            step++;
            convgMsg[1] = step;
        }
        
        if(convgMsg[1] > maxStep)
            convgMsg[0] = 2;
            
        // Return convergence message:
        // -1: rule does not affect configuration any more
        //  0: converge to 0 at Mth step
        //  1: converge to 1 at Mth step
        //  2: no convergence till maxStep
        return convgMsg;
    }
    
//----------------------------------------------------------------------
// Supplemental methods: data-type convertion
//----------------------------------------------------------------------
    /* Convert a integer to a bit-string (stored in a int-string) */
    public int[] intToBitArray(final int bitLength, final int x)
    {
        int[] bitArray = new int[bitLength];
        int tmp = x;
        // Convert i into n-bit binary string
        for(int j=bitLength; j>0; j--)
        {
            bitArray[j-1] = tmp%2;  // If the remainder is 1, then this bit is 1
            tmp = tmp/2;            // divided by 2 and drop remainder, to move one bit left-ward
        }
        return bitArray;
    }

    /* Convert a bit-string (stored in a int-string) to an integer*/
    public int bitArrayToInt(final int[] bitArray)
    {
        int x = 0;
        int bl = bitArray.length;
        // Convert bitArray to an integer:
        //   x = 2^n*bitArray[0] + 2^(n-1)*bitArray[1] +....+ 2^0*bitArray[n]
        for(int j = 0; j < bl; j++)
        {
            x += bitArray[j]* (int)Math.pow(2.,(double)(bl-j-1));  
        }
        return x;
    }

    /* Convert an integer array to a string for output*/
    public String intArrayToString(final int[] intArray)
    {
        String output = new String();
        for (int i = 0; i < intArray.length; i++){
           output = output + " " + intArray[i];
        }
        return(output);
    }

    /* Check if two integer arrays are equal */
    public boolean isTwoConfigEqual(final int[] conf1, final int[] conf2)
    {
        // Check: 2 config should have the same length
        if (conf1.length!=conf2.length)
        {
            System.out.println("\nLength of two configurations are not the same, can not be compared!");
            return false;
        }

        boolean output = true;
        for (int i = 0; i < conf1.length; i++){
            if (conf1[i]!=conf2[i])
            {
                output = false;
                break;
            }
        }
        return(output);
    }

    /* Copy integer array */
    public int[] copyIntArray(final int[] a1)
    {
        int[] a2 = new int[a1.length];
        for (int i = 0; i < a1.length; i++){
            a2[i] = a1[i];
        }
        return(a2);
    }

    /* Sum up integer array */
    public int sumIntArray(final int[] a1)
    {
        int sum = 0;
        for (int i = 0; i < a1.length; i++){
            sum += a1[i];
        }
        return(sum);
    }
    
}
